#include <stdlib.h>
int countPrimes(int n)
{
  int count = 0;
  int *isPrime = (int *)malloc(n * (sizeof(int)));
  for (int i = 2; i < n; i++)
  { // 下标表示第几个数的话，刚好这个数组就可以表示小于n的数
    isPrime[i] = 1;
  }

  for (int i = 2; i < n; i++)
  {
    if (isPrime[i] == 1)
    {
      count++;
      if ((long)i * i < n)
      {
        for (int j = i * i; j < n; j += i)
        {
          isPrime[j] = 0;
        }
      }
    }
  }
  return count;
}
// 2 是最小的一个质数

// 并且每一个 x * 非1 和 非他本身那就不是质数
// x * y = z (y！=1 or y!=x) z 不是质数

// 当我们遇到一个质数x的时候就可以将后面所有x*i=k 都标记一下，表示他不是质数
// 2*2 2*3 2*4 小于n的那个数为止 ，
// 3*2 3*3 3*4
// 4*4

// 判断一个数是否是质数 返回0表示不是质数，返回1表示是质数
int isPrime(int x)
{
  // 一个数只能被1和它本身整除那就是质数
  for (int i = 2; i < x; i++)
  {
    if (x % i == 0)
    { // 3%2==1
      return 0;
    }
  }
  return 1;
}